package com.ywk.base.dataStructure.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/*快速排序：冒泡的升级版，规定一个数为基数，大于该数的放到该数左边，
小于该数的放到该数右边，用递归不断的的重复（从小到大）*/
public class QuicklySort {

	public static void main(String[] args) {
		//int[] nums={6,3,5,4,8,1,7,2,15,55,21,84,12};
		int[] nums= {1,6,3,4,9,5,2,8,0};
//		int[] nums = new int[8000000];
//		for (int i = 0; i < nums.length; i++) {
//			nums[i] = (int) (Math.random() * 8000000);
//		}
		Date d1 = new Date();
		SimpleDateFormat s = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");// 日期格式
		System.out.println("排序前的时间：" + s.format(d1));
		quicklySort(nums, 0, nums.length - 1);
//		System.out.println(Arrays.toString(nums));
		Date d2 = new Date();
		System.out.println("排序后的时间：" + s.format(d2));

	}

	public static void quicklySort(int[] nums, int left, int right) {
		int start = left;
		int end = right;
		int key = nums[left]; 
		 while(end>start){
		 //从后往前比较
			 while(end>start&&nums[end]>=key) {//找比关键之小的
				 //如果没有比关键值小的，比较下一个，直到有比关键值小的交换位置，然后又从前往后比较
				 end--; 
			 }
			 if(end>start&&nums[end]<=key){
				 int temp = nums[end];
				 nums[end] = nums[start];
				 nums[start] = temp;
			 }
			 //从前往后比较
			 while(end>start&&nums[start]<=key) {//找比关键之大的
				 //如果没有比关键值大的，比较下一个，直到有比关键值大的交换位置
				 start++; 
			 }
			 if(end>start&&nums[start]>=key){
				 int temp = nums[start];
				 nums[start] = nums[end];
				 nums[end] = temp;
			 }
			 //此时第一次循环比较结束，关键值的位置已经确定了。左边的值都比关键值小，右边的
			 //值都比关键值大，但是两边的顺序还有可能是不一样的，进行下面的递归调用
			 System.out.println(Arrays.toString(nums));
		 }
		 //递归
		 if(start>left) quicklySort(nums,left,start-1);//左边序列 。第一个索引位置到关键值索引-1
		 if(end<right) quicklySort(nums,end+1,right);//右边序列。从关键值索引+1 到最后一个
		
		
		
//		if(nums != null && nums.length > 0) {
//			int start = left, end = right;
//			//target是本次循环要排序的元素，每次循环都是确定一个元素的排序位置，这个元素都是开始下标对应的元素
//			int target = nums[left];
//			//开始循环，从两头往中间循环，相遇后循环结束
//			while(start<end) {
//				//从右向左循环比较，如果比target小，就和target交换位置，让所有比target小的元素到target的左边去
//				while(start < end) {
//					if(nums[end] < target) {
//						int temp=nums[start];
//						nums[start]=nums[end];
//						nums[end]=temp;
//						break;
//					}else {
//						end--;
//					}
//				}
//				//从左向右循环比较，如果比target大，就和target交换位置，让所有比target大的元素到target的右边去
//				while(start < end) {
//					if(nums[start] > target) {
//						int temp=nums[start];
//						nums[start]=nums[end];
//						nums[end]=temp;
//						break;
//					}else {
//						start++;
//					}
//				}
//			}
//			//确定target的排序后，如果target左边还有元素，继续递归排序
//			if((start-1)>left) {
//				quicklySort(nums, left, start-1);
//			}
//			//确定target的排序后，如果target右边还有元素，继续递归排序
//			if((end+1)<right) {
//				quicklySort(nums, end+1, right);
//			}
//		}
		
//		int l = left;//左指针（最左）
//		int r = right;//右指针（最右）
//		int pivot = nums[(l + r) / 2];
//		while (l < r) {
//			while (nums[l] > pivot) {
//				l++;
//			}
//			while (nums[r] < pivot) {
//				r--;
//			}
//			if (l >= r) {
//				break;
//			}
//			int temp = nums[l];
//			nums[l] = nums[r];
//			nums[r] = temp;
//			if (nums[l] == pivot) {
//				r--;
//			}
//			if (nums[r] == pivot) {
//				l++;
//			}
//		}
//		// System.out.println(Arrays.toString(nums));
//		if (l == r) {
//			l++;
//			r--;
//		}
//		if (left < r) {
//			quicklySort(nums, left, r);
//		}
//		if (l < right) {
//			quicklySort(nums, l, right);
//		}
	}
}
